package com.lun.swordtowardoffer2.c14;

public class UniquePaths {
	
	//方法二：动态规划（递归版）
	public int uniquePaths(int m, int n) {
		int[][] dp = new int[m][n];
		return helper(m - 1, n - 1, dp);
	}
	
	private int helper(int i, int j, int[][] dp) {
		if(dp[i][j] == 0) {
			if(i == 0 || j == 0) {
				dp[i][j] = 1;
			}else {
				dp[i][j] = helper(i - 1, j, dp) + helper(i, j - 1, dp);
			}
		}
		return dp[i][j];
	}

	//方法二：动态规划（迭代版）
	public int uniquePaths2(int m, int n) {
		int[][] dp = new int[m][n];
		
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (i == 0 || j == 0) {
					dp[i][j] = 1;
				} else {
					dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
				}
			}
		}
		return dp[m - 1][n - 1];
	}
	
	
	//方法二：动态规划（迭代版）（优化）
	public int uniquePaths3(int m, int n) {
		int[] dp = new int[n];

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (i == 0) {
					dp[j] = 1;
				} else if (j > 0) {
					dp[j] += dp[j - 1];
				}
			}
		}

		return dp[n - 1];
	}
}
